package algorithm.leetcode.simple;

/*
 给定一棵二叉树，你需要计算它的直径长度。一棵二叉树的直径长度是任意两个结点路径长度中的最大值。
 这条路径可能穿过也可能不穿过根结点。
 */

/**
 * @author jack.wu
 * @version 1.0
 * @date 2020/10/29
 */
public class Question543 {

    public static void main(String[] args) {

    }

    int r;

    public int diameterOfBinaryTree(TreeNode root) {
        r = 1;
        depth(root);
        return r - 1;
    }

    private int depth(TreeNode node) {
        if (node == null) {
            return 0;
        }
        int leftPath = depth(node.left);
        int rightPath = depth(node.right);
        // 直径
        r = Math.max(r, leftPath + rightPath + 1);
        // 深度
        return Math.max(leftPath, rightPath) + 1;
    }


    private static class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;

        TreeNode(int x) {
            val = x;
        }
    }
}
